package tree.heap.arrayUse0IndexHeap;

/**
 * 功能描述: 小顶堆: 堆顶元素最小 , 大顶堆与小顶堆 无非就是改变比较规则:不同的比价器
 * 2024/05/27
 * <p>
 * ZhangYi
 */
public class MinTopHeapArrayUtils {

    public static void main(String[] args) {
        int  maxLength = 100;
        int maxValues = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            int[] arr= generateRandomArray(maxLength,maxValues);
            int[] arr2 = copyArray(arr);
            // 堆排序
            heapSort(arr);
            insertSort(arr2);
            if (!isEqualArray(arr,arr2)){
                System.out.println("测试未通过,Has Error");
                //System.out.println(arr);
                //System.out.println(arr2);
                break;
            }
        }
        System.out.println("Sucess! 测试通过");
    }

    private static boolean isEqualArray(int[] arr,
                                        int[] arr2) {
        if (arr == null ^ arr2 == null ){
            return false;
        }
        if (arr == null && arr2 == null ){
            return true;
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    private static void insertSort(int[] arr2) {
        // 如果数组为空或者数组长度为1， 就不需要排序,直接返回
        if (arr2 == null || arr2.length<2){
            return;
        }

        for (int index = 1; index < arr2.length; index++) {
            // 倒序排列
            for (int j = index ; j > 0 && arr2[j]>arr2[j-1]; j--){
                swap(arr2,j,j-1);
            }
        }
    }

    private static int[] copyArray(int[] arr) {
        if (arr == null){
            return null;
        }
        int[] arr2 = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr2[i] = arr[i];
        }
        return arr2;
    }

    private static int[] generateRandomArray(int maxLength,
                                             int maxValues) {
        int[] arr = new int[(int) (Math.random() * maxLength)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * maxValues);
        }
        return arr;
    }

    /**
     * 功能描述: 堆排序
     *
     * @param arr arr
     */
    private static void heapSort(int[] arr) {
        if (arr == null || arr.length <2){
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr,i);
        }

        int heapSize = arr.length;
        // 最小值移到堆尾, 做了一个隔离, 然后交换到堆尾, 至此队尾的元素不在访问
        swap(arr,0,--heapSize);

        while (heapSize > 0){
            heapfiy(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }

    }

    /**
     * 功能描述: 堆化, 在堆内的元素发生改变的时候, 需要重新堆化,选举一个最小的值出现在堆顶 索引0的位置
     *
     * @param arr      arr
     * @param index    索引
     * @param heapSize 堆大小
     */
    private static void heapfiy(int[] arr,
                                int index,
                                int heapSize) {
        int leftIndex = (index<<1) | 1;

        while (leftIndex < heapSize) {
            // 注意这里的边界条件, 是不一样的, 一个明显的指出了  没有处理越界
            //int smallestIndex = leftIndex +1 < heapSize && arr[leftIndex] < arr[leftIndex+1] ? leftIndex: leftIndex+1;

            // 处理了越界问题 , 在右子树没有越界且 右子树 < 左子树 的情况下获取一个最小值的索引
            int smallestIndex = leftIndex +1 < heapSize && arr[leftIndex+1] < arr[leftIndex] ? leftIndex+1: leftIndex;

            smallestIndex = arr[index] < arr[smallestIndex] ? index : smallestIndex;

            if (index == smallestIndex){
                return;
            }
            swap(arr,index,smallestIndex);
            index = smallestIndex;
            leftIndex = (index<<1) | 1;
        }
    }

    /**
     * 功能描述: 插入堆,插入的同时维持一个一个小顶堆
     *
     * @param arr   arr
     * @param index 索引
     */
    private static void heapInsert(int[] arr,
                                   int index) {

        while (arr[index]< arr[(index-1)/2]){
            swap(arr,index,(index-1)/2);
            index = (index-1)/2; // 更新index
        }
    }

    private static void swap(int[] arr,
                             int index,
                             int index2) {

        int temp = arr[index];
        arr[index] = arr[index2];
        arr[index2] = temp;
    }
}
